package org.xqh.study.leetcode.algorithm.accountmerge;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONArray;
import org.springframework.util.StopWatch;

import java.util.*;
import java.util.Map.Entry;
import java.util.stream.Collectors;

/**
 * @ClassName AccountMergeTeest
 * @Description 账号合并
 * @Author xuqianghui
 * @Date 2021/1/18 9:33
 * @Version 1.0
 */
public class AccountMergeTest {

    public static void main(String[] args) {
//        String str = "[[\"John\",\"johnsmith@mail.com\",\"john_newyork@mail.com\"],[\"John\",\"johnsmith@mail.com\",\"john00@mail.com\"],[\"Mary\",\"mary@mail.com\"],[\"John\",\"johnnybravo@mail.com\"]]";
//        String str = "[[\"Alex\",\"Alex5@m.co\",\"Alex4@m.co\",\"Alex0@m.co\"],[\"Ethan\",\"Ethan3@m.co\",\"Ethan3@m.co\",\"Ethan0@m.co\"],[\"Kevin\",\"Kevin4@m.co\",\"Kevin2@m.co\",\"Kevin2@m.co\"],[\"Gabe\",\"Gabe0@m.co\",\"Gabe3@m.co\",\"Gabe2@m.co\"],[\"Gabe\",\"Gabe3@m.co\",\"Gabe4@m.co\",\"Gabe2@m.co\"]]";
        String str = "[[\"Fern\",\"Fern8@m.co\",\"Fern9@m.co\"],[\"Fern\",\"Fern7@m.co\",\"Fern8@m.co\"],[\"Fern\",\"Fern4@m.co\",\"Fern5@m.co\"],[\"Fern\",\"Fern10@m.co\",\"Fern11@m.co\"],[\"Fern\",\"Fern9@m.co\",\"Fern10@m.co\"],[\"Fern\",\"Fern6@m.co\",\"Fern7@m.co\"],[\"Fern\",\"Fern1@m.co\",\"Fern2@m.co\"],[\"Fern\",\"Fern11@m.co\",\"Fern12@m.co\"],[\"Fern\",\"Fern3@m.co\",\"Fern4@m.co\"],[\"Fern\",\"Fern2@m.co\",\"Fern3@m.co\"],[\"Fern\",\"Fern5@m.co\",\"Fern6@m.co\"],[\"Fern\",\"Fern0@m.co\",\"Fern1@m.co\"]]";
        StopWatch watch = new StopWatch("cost time");
        watch.start("merge account");
//        String str = ReadTxtFileUtils.readJson(new File("E:\\document\\yzs\\program\\accountMerge.txt"));
        List<List> list = JSONArray.parseArray(str, List.class);
        System.out.println(JSON.toJSONString(list));
        System.out.println(JSON.toJSONString(accountsMerge(list)));
//        watch.stop();
//        System.out.println(watch.prettyPrint());
    }

    public static List<List<String>> accountsMerge(List<List> accounts) {
        Map<String, Integer> emailToIndex = new HashMap<String, Integer>();
        Map<String, String> emailToName = new HashMap<String, String>();
        int emailsCount = 0;//邮箱编号
        for (List<String> account : accounts) {
            String name = account.get(0);
            int size = account.size();
            for (int i = 1; i < size; i++) {
                String email = account.get(i);
                if (!emailToIndex.containsKey(email)) {
                    emailToIndex.put(email, emailsCount++);
                    emailToName.put(email, name);
                }
            }
        }
        UnionFind uf = new UnionFind(emailsCount);
        for (List<String> account : accounts) {
            String firstEmail = account.get(1);
            int firstIndex = emailToIndex.get(firstEmail);
            int size = account.size();
            for (int i = 2; i < size; i++) {
                String nextEmail = account.get(i);
                int nextIndex = emailToIndex.get(nextEmail);
                uf.union(firstIndex, nextIndex);
            }
        }
        Map<Integer, List<String>> indexToEmails = new HashMap<Integer, List<String>>();
        for (String email : emailToIndex.keySet()) {
            int index = uf.find(emailToIndex.get(email));
            List<String> account = indexToEmails.getOrDefault(index, new ArrayList<String>());
            account.add(email);
            indexToEmails.put(index, account);
        }
        List<List<String>> merged = new ArrayList<List<String>>();
        for (List<String> emails : indexToEmails.values()) {
            Collections.sort(emails);
            String name = emailToName.get(emails.get(0));
            List<String> account = new ArrayList<String>();
            account.add(name);
            account.addAll(emails);
            merged.add(account);
        }
        return merged;
    }

    public static class UnionFind {
        int[] parent;

        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public void union(int index1, int index2) {
            parent[find(index2)] = find(index1);
        }

        /**
         * 找 对应根节点 邮箱编号
         * @param index
         * @return
         */
        public int find(int index) {
            if (parent[index] != index) {
                parent[index] = find(parent[index]);
            }
            return parent[index];
        }
    }


    /**
     * &#x5E76;&#x67E5;&#x96C6; &#x65B9;&#x5F0F;
     *
     * @param accounts
     * @return
     */
    public static List<List<String>> accountsMerge3(List<List> accounts) {
        List<String> nameList = new ArrayList<>(accounts.size());
        List<TestModel> treeList = new ArrayList<>(accounts.size());
        for (int i = 0; i < accounts.size(); i++) {
            List<String> item = accounts.get(i);
            nameList.add(item.get(0));
            List<TestModel> idxList = new ArrayList<>();
            for (int j = 1; j < item.size(); j++) {
                idxList.add(new TestModel(item.get(j), i));
            }
        }
        return null;
    }

    /**
     * https://leetcode-cn.com/problems/accounts-merge/
     *
     * @param accounts
     * @return
     */
    public static List<List<String>> accountsMerge2(List<List> accounts) {
        List<String> nameList = new ArrayList<>(accounts.size());
        Map<String, Integer> emailMap = new HashMap<>(accounts.size());
        List<TestModel> list = new ArrayList<>();
        Map<Integer, List<TestModel>> idxMap = new HashMap<>();
        for (int i = 0; i < accounts.size(); i++) {
            List<String> item = accounts.get(i);
            nameList.add(item.get(0));
            List<TestModel> idxList = new ArrayList<>();
            for (int j = 1; j < item.size(); j++) {
                idxList.add(new TestModel(item.get(j), i));
            }
            idxMap.put(i, idxList);
            list.addAll(idxList);
        }
        list.sort((a, b) -> a.getEmail().compareTo(b.getEmail()));
        for (TestModel t : list) {
            if (emailMap.containsKey(t.getEmail())) {
                List<TestModel> items = idxMap.get(t.getNameIdx());
                Integer idx = emailMap.get(t.getEmail());
                items.stream().forEach(it -> {
                    recursionFindLinkEmail(list, emailMap, it, idxMap, idx);
                });
            } else {
                emailMap.put(t.getEmail(), t.getNameIdx());
            }
        }
        List<List<String>> result = new ArrayList<>(accounts.size());
        Map<Integer, List<String>> idxMap2 = new HashMap<>();
        for (Entry<String, Integer> entry : emailMap.entrySet()) {
            if (idxMap2.containsKey(entry.getValue())) {
                idxMap2.get(entry.getValue()).add(entry.getKey());
            } else {
                List<String> items = new ArrayList<>();
                items.add(entry.getKey());
                idxMap2.put(entry.getValue(), items);
            }
        }
        for (Entry<Integer, List<String>> entry : idxMap2.entrySet()) {
            List<String> items = new ArrayList<>();
            items.add(nameList.get(entry.getKey()));
            entry.getValue().sort((a, b) -> a.compareTo(b));
            items.addAll(entry.getValue());
            result.add(items);
        }
        return result;
    }

    public static void recursionFindLinkEmail(List<TestModel> list, Map<String, Integer> emailMap, TestModel t, Map<Integer, List<TestModel>> idxMap, Integer extIdx) {
        if (t.isUse()) {
            return;
        }
        t.setUse(true);
        emailMap.put(t.getEmail(), extIdx);
        List<TestModel> filter = list.stream().filter(l -> l.getEmail().equals(t.getEmail()) && !l.isUse()).collect(Collectors.toList());
        if (filter.size() > 0) {
            filter.stream().forEach(c -> {
                c.setUse(true);
                List<TestModel> clist = idxMap.get(c.getNameIdx()).stream().filter(cl -> !cl.isUse()).collect(Collectors.toList());
                if (clist.size() > 0) {
                    clist.stream().forEach(ci -> {
                        recursionFindLinkEmail(list, emailMap, ci, idxMap, extIdx);
                    });
                }
            });
        }
    }

public static class TestModel {
    private String email;
    private Integer nameIdx;
    private boolean use;
    private TestModel parent;

    public TestModel(String email, Integer nameIdx) {
        this.email = email;
        this.nameIdx = nameIdx;
    }

    public TestModel getParent() {
        return parent;
    }

    public void setParent(TestModel parent) {
        this.parent = parent;
    }

    public String getEmail() {
        return email;
    }

    public boolean isUse() {
        return use;
    }

    public void setUse(boolean use) {
        this.use = use;
    }

    public void setEmail(String email) {
        this.email = email;
    }

    public Integer getNameIdx() {
        return nameIdx;
    }

    public void setNameIdx(Integer nameIdx) {
        this.nameIdx = nameIdx;
    }
}
}
